
/*
    Copyright (C) 1999-2008 by Mark D. Hill and David A. Wood for the
    Wisconsin Multifacet Project.  Contact: gems@cs.wisc.edu
    http://www.cs.wisc.edu/gems/

    --------------------------------------------------------------------

    This file is part of the Ruby Multiprocessor Memory System Simulator, 
    a component of the Multifacet GEMS (General Execution-driven 
    Multiprocessor Simulator) software toolset originally developed at 
    the University of Wisconsin-Madison.

    Ruby was originally developed primarily by Milo Martin and Daniel
    Sorin with contributions from Ross Dickson, Carl Mauer, and Manoj
    Plakal.

    Substantial further development of Multifacet GEMS at the
    University of Wisconsin was performed by Alaa Alameldeen, Brad
    Beckmann, Jayaram Bobba, Ross Dickson, Dan Gibson, Pacia Harper,
    Derek Hower, Milo Martin, Michael Marty, Carl Mauer, Michelle Moravan,
    Kevin Moore, Andrew Phelps, Manoj Plakal, Daniel Sorin, Haris Volos, 
    Min Xu, and Luke Yen.
    --------------------------------------------------------------------

    If your use of this software contributes to a published paper, we
    request that you (1) cite our summary paper that appears on our
    website (http://www.cs.wisc.edu/gems/) and (2) e-mail a citation
    for your published paper to gems@cs.wisc.edu.

    If you redistribute derivatives of this software, we request that
    you notify us and either (1) ask people to register with us at our
    website (http://www.cs.wisc.edu/gems/) or (2) collect registration
    information and periodically send it to us.

    --------------------------------------------------------------------

    Multifacet GEMS is free software; you can redistribute it and/or
    modify it under the terms of version 2 of the GNU General Public
    License as published by the Free Software Foundation.

    Multifacet GEMS is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with the Multifacet GEMS; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307, USA

    The GNU General Public License is contained in the file LICENSE.

### END HEADER ###
*/

/*
 * Set.C
 * 
 * Description: See Set.h
 *
 * $Id: BigSet.C 1.9 05/01/19 13:12:25-06:00 mikem@maya.cs.wisc.edu $
 *
 */

// modified (rewritten) 05/20/05 by Dan Gibson to accomimdate FASTER >32 bit
// set sizes

#include "Set.h"
#include "RubyConfig.h"

#if __amd64__ || __LP64__
#define __64BITS__ 
#else
#define __32BITS__ 
#endif

Set::Set()
{ 
  m_p_nArray = NULL;
  setSize(RubyConfig::numberOfProcessors());
}

// copy constructor
Set::Set(const Set& obj) {
  m_p_nArray = NULL;
  setSize(obj.m_nSize);

  // copy from the host to this array
  for(int i=0; i<m_nArrayLen; i++) {
    m_p_nArray[i] = obj.m_p_nArray[i];
  }

}

Set::Set(int size)
{
  m_p_nArray = NULL;
  assert(size>0);       
  setSize(size);
}

Set::~Set() {
  if( (m_p_nArray != (&m_p_nArray_Static[0])) && (m_p_nArray != NULL)) 
    delete [] m_p_nArray;
  m_p_nArray = NULL;
}


// /*
//  * This function should set the bit corresponding to index
//  * to 1.
//  */

// void Set::add(NodeID index)
// {
//   assert(index<m_nSize && index >= 0);
  
// #ifdef __32BITS__
//   m_p_nArray[index>>5] |= (1 << (index & 0x01F));       
// #else
//   m_p_nArray[index>>6] |= (((unsigned long) 1) << (index & 0x03F));
// #endif // __32BITS__ 

// }

/*
 * This function should set all the bits in the current set
 * that are already set in the parameter set
 */
void Set::addSet(const Set& set)
{
  assert(getSize()==set.getSize());
  for(int i=0; i<m_nArrayLen; i++) {
    m_p_nArray[i] |= set.m_p_nArray[i];
  }

}

/*
 * This function should randomly assign 1 to the bits in the set--
 * it should not clear the bits bits first, though?
 */
void Set::addRandom()
{
  
  for(int i=0; i<m_nArrayLen; i++) {
    m_p_nArray[i] |= random() ^ (random() << 4); // this ensures that all 32 bits are subject to random effects,
                                                 // as RAND_MAX typically = 0x7FFFFFFF
  } 
 
  // now just ensure that no bits over the maximum size were set
#ifdef __32BITS__
  long mask = 0x7FFFFFFF;

  // the number of populated spaces in the higest-order array slot is:
  // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
  // cleared

  if((m_nSize % 32) != 0) {
    for(int j=0; j<32-(m_nSize&0x01F); j++) {
      m_p_nArray[m_nArrayLen-1] &= mask;
      mask = mask >> 1;
    }
  }
#else
  long mask = 0x7FFFFFFFFFFFFFFF;

  // the number of populated spaces in the higest-order array slot is:
  // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
  // cleared

  if((m_nSize % 64) != 0) {
    for(int j=0; j<64-(m_nSize&0x03F); j++) {
      m_p_nArray[m_nArrayLen-1] &= mask;
      mask = mask >> 1;
    }
  }
#endif // __32BITS__
 
}

// /*
//  * This function unsets the bit associated with index
//  */
// void Set::remove(NodeID index)
// {
//   assert(index<m_nSize && index>=0);

// #ifdef __32BITS__
//   m_p_nArray[index>>5] &= ~(0x00000001         << (index & 0x01F));     
// #else
//   m_p_nArray[index>>6] &= ~(((unsigned long) 0x0000000000000001) << (index & 0x03F));
// #endif // __32BITS__

// }


/*
 * This function clears bits that are =1 in the parameter set
 */
void Set::removeSet(const Set& set)
{
  
  assert(m_nSize==set.m_nSize);
  for(int i=0; i<m_nArrayLen; i++) {
    m_p_nArray[i] &= ~(set.m_p_nArray[i]);
  }
  
}

// /*
//  * This function clears all bits in the set
//  */
// void Set::clear()
// {
//   for(int i=0; i<m_nArrayLen; i++) {
//     m_p_nArray[i] = 0;
//   }
// }

/*
 * this function sets all bits in the set
 */
void Set::broadcast()
{
        
  for(int i=0; i<m_nArrayLen; i++) {
    m_p_nArray[i] = -1; // note that -1 corresponds to all 1's in 2's comp.
  }
        
  // now just ensure that no bits over the maximum size were set
#ifdef __32BITS__
  long mask = 0x7FFFFFFF;

  // the number of populated spaces in the higest-order array slot is:
  // m_nSize % 32, so the uppermost 32 - m_nSize%32 bits should be
  // cleared

  if((m_nSize % 32) != 0) {
    for(int j=0; j<32-(m_nSize&0x01F); j++) {
      m_p_nArray[m_nArrayLen-1] &= mask;
      mask = mask >> 1;
    }
  }
#else
  long mask = 0x7FFFFFFFFFFFFFFF;

  // the number of populated spaces in the higest-order array slot is:
  // m_nSize % 64, so the uppermost 64 - m_nSize%64 bits should be
  // cleared

  if((m_nSize % 64) != 0) {
    for(int j=0; j<64-(m_nSize&0x03F); j++) {
      m_p_nArray[m_nArrayLen-1] &= mask;
      mask = mask >> 1;
    }
  }
#endif // __32BITS__  
  
}

/*
 * This function returns the population count of 1's in the set
 */
int Set::count() const
{
  int counter = 0;
  long mask;
  for( int i=0; i<m_nArrayLen; i++) {
    mask = (long) 0x01;

#ifdef __32BITS__
    for( int j=0; j<32; j++) {
      if(m_p_nArray[i] & mask) counter++;
      mask = mask << 1;
    }
    
#else
    
    for( int j=0; j<64; j++) {  // FIXME - significant performance loss when array population << 64
      if((m_p_nArray[i] & mask) != 0) {
              counter++;
      }
      mask = mask << 1;
    }
    
#endif // __32BITS__
    
  }

  return counter;
}

/*
 * This function checks for set equality
 */

bool Set::isEqual(const Set& set) const
{
  assert(m_nSize==set.m_nSize);

  for(int i=0;i<m_nArrayLen;i++) {
    if(m_p_nArray[i] != set.m_p_nArray[i]) {
      return false;
    }
  }  

  return true;
}

/*
 * This function returns the NodeID (int) of the 
 * least set bit
 */
NodeID Set::smallestElement() const
{
  assert(count() > 0);
  long x;
  for( int i=0; i<m_nArrayLen; i++) {
    if(m_p_nArray[i]!=0) {
      // the least-set bit must be in here
      x = m_p_nArray[i];

#ifdef __32BITS__
      for( int j=0; j<32; j++) {
        if(x & 0x00000001) {
          return 32*i+j;
        }
        
        x = x >> 1;
      }
#else
      for( int j=0; j<64; j++) {
        if(x & 0x0000000000000001) {
          return 64*i+j;
        }

        x = x >> 1;
      }
#endif // __32BITS__

      ERROR_MSG("No smallest element of an empty set.");
    }
  }

  ERROR_MSG("No smallest element of an empty set.");
  
  return 0;
}

/*
 * this function returns true iff all bits are set
 */
bool Set::isBroadcast() const
{
  // check the fully-loaded words by equal to 0xffffffff
  // only the last word may not be fully loaded, it is not
  // fully loaded iff m_nSize % 32 or 64 !=0 => fully loaded iff
  // m_nSize % 32 or 64 == 0

#ifdef __32BITS__
  for(int i=0; i< (((m_nSize % 32)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
    if(m_p_nArray[i]!=-1) {
      return false;
    }
  }

  // now check the last word, which may not be fully loaded
  long mask = 1;
  for(int j=0; j< (m_nSize % 32); j++) {
    if((mask & m_p_nArray[m_nArrayLen-1])==0) {
      return false;
    }
    mask = mask << 1;
  }
#else
  for(int i=0; i< (((m_nSize % 64)==0) ? m_nArrayLen : m_nArrayLen-1); i++) {
    if(m_p_nArray[i]!=-1) {
      return false;
    }
  }

  // now check the last word, which may not be fully loaded
  long mask = 1;
  for(int j=0; j< (m_nSize % 64); j++) {
    if((mask & m_p_nArray[m_nArrayLen-1])==0) {
      return false;
    }
    mask = mask << 1;
  }

#endif // __32BITS__
  
  return true;
}

/*
 * this function returns true iff no bits are set
 */
bool Set::isEmpty() const
{
        
  // here we can simply check if all = 0, since we ensure
  // that "extra slots" are all zero
  for(int i=0; i< m_nArrayLen ; i++) {
    if(m_p_nArray[i]!=0) {
            return false;
    }
  }

  return true;
}

// returns the logical OR of "this" set and orSet 
Set Set::OR(const Set& orSet) const
{
  Set result(m_nSize);
  assert(m_nSize == orSet.m_nSize);
  for(int i=0; i< m_nArrayLen; i++) {
    result.m_p_nArray[i] = m_p_nArray[i] | orSet.m_p_nArray[i];
  }
 
  return result;

}

// returns the logical AND of "this" set and andSet 
Set Set::AND(const Set& andSet) const
{
  Set result(m_nSize);
  assert(m_nSize == andSet.m_nSize);
  
  for(int i=0; i< m_nArrayLen; i++) {
    result.m_p_nArray[i] = m_p_nArray[i] & andSet.m_p_nArray[i];
  }
  
  return result;
}

// // Returns true if the intersection of the two sets is non-empty
// bool Set::intersectionIsNotEmpty(const Set& other_set) const
// {
//   assert(m_nSize == other_set.m_nSize);
//   for(int i=0; i< m_nArrayLen; i++) {
//     if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
//       return true;
//     }
//   }

//   return false;

// }

// // Returns true if the intersection of the two sets is empty
// bool Set::intersectionIsEmpty(const Set& other_set) const
// {
//   assert(m_nSize == other_set.m_nSize);
//   for(int i=0; i< m_nArrayLen; i++) {
//     if(m_p_nArray[i] & other_set.m_p_nArray[i]) {
//       return false;
//     }
//   }

//   return true;

// }

/*
 * Returns false if a bit is set in the parameter set that is
 * NOT set in this set
 */
bool Set::isSuperset(const Set& test) const
{
  assert(m_nSize == test.m_nSize);

  for(int i=0;i<m_nArrayLen;i++) {
    if(((test.m_p_nArray[i] & m_p_nArray[i]) | ~test.m_p_nArray[i]) != -1) {
      return false;
    }
  }
  
  return true;
}

// /*
//  * Returns true iff this bit is set
//  */
// bool Set::isElement(NodeID element) const
// {
//   bool result;

// #ifdef __32BITS__
//   result = ((m_p_nArray[element>>5] & (0x00000001         << (element & 0x01F)))!=0);   
// #else
//   result = ((m_p_nArray[element>>6] & (((unsigned long) 0x0000000000000001) << (element & 0x03F)))!=0);
// #endif // __32BITS__

//   return result;
// }

/*
 * "Supposed" to return the node id of the (n+1)th set
 * bit, IE n=0 => returns nodeid of first set bit, BUT
 * since BigSet.C behaves strangely, this implementation
 * will behave strangely just for reverse compatability.
 *
 * Was originally implemented for the flight data recorder
 * FDR
 */

// NodeID Set::elementAt(int n) const
// { 
//   if(isElement(n)) return (NodeID) true;
//   else return 0;
        
// /*      
//   int match = -1;
//   for(int i=0;i<m_nSize;i++) {
//     if(isElement(i)) match++;
//     if(match==n) {
//       return i;
//     }
//   } 
  
//   return -1;
//   */
// }

void Set::setSize(int size) 
{
  m_nSize = size;

#ifdef __32BITS__
  m_nArrayLen = m_nSize/32 + ((m_nSize%32==0) ? 0 : 1 );
#else
  m_nArrayLen = m_nSize/64 + ((m_nSize%64==0) ? 0 : 1 );
#endif // __32BITS__
  
  // decide whether to use dynamic or static alloction
  if(m_nArrayLen<=NUMBER_WORDS_PER_SET) { // constant defined in RubyConfig.h
    // its OK to use the static allocation, and it will
    // probably be faster (as m_nArrayLen is already in the
    // cache and they will probably share the same cache line)

    // if switching from dyanamic to static allocation (which
    // is probably rare, but why not be complete?), must delete
    // the dynamically allocated space
    if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0]))
      delete [] m_p_nArray;
    
    m_p_nArray = & m_p_nArray_Static[0];
  } else {

    // can't use static allocation...simply not enough room
    // so dynamically allocate some space
    if((m_p_nArray != NULL) && (m_p_nArray != &m_p_nArray_Static[0]))
      delete [] m_p_nArray;
    
    m_p_nArray = new long[m_nArrayLen];
  }
  
  clear();
}

Set& Set::operator=(const Set& obj) {
  if(this == &obj) {
    // do nothing
  } else {
    
    // resize this item
    setSize(obj.getSize());

    // copy the elements from obj to this
    for(int i=0; i<m_nArrayLen; i++) {
      m_p_nArray[i] = obj.m_p_nArray[i];
    }
  }

  return *this;
}

void Set::print(ostream& out) const
{
  if(m_p_nArray==NULL) {
    out << "[Set {Empty}]";
    return;
  }
  char buff[24];
  out << "[Set 0x ";
  for (int i=m_nArrayLen-1; i>=0; i--) { 
#ifdef __32BITS__
    sprintf(buff,"%08X ",m_p_nArray[i]);
#else
    sprintf(buff,"0x %016llX ",m_p_nArray[i]);  
#endif // __32BITS__
    out << buff;
  }
  out << " ]";

}


